#include "letterCombinations.h"
void dfsCombination(std::vector<std::string> &infos, int start, std::string str,
                    std::vector<std::string> &cache) {
    if (start == infos.size()) {
        cache.push_back(str);
    } else {
        for (auto e : infos[start]) {
            dfsCombination(infos, start + 1, str + e, cache);
        }
    }
}

std::vector<std::string> letterCombinations(std::string digits) {
    std::string a[9] = {"abc", "def",  "ghi", "jkl",
                        "mno", "pqrs", "tuv", "wxyz"};
    std::vector<std::string> result;
    if (digits.size() == 0)
        return result;
    else {
        std::vector<std::string> infos;
        for (auto ch : digits) {
            infos.push_back(a[ch - '0' - 2]);
        }
        dfsCombination(infos, 0, "", result);
        return result;
    }
}
